package com.lw.leetcode.dp.c;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1713. 得到子序列的最少操作次数
 * binay
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/16 14:37
 */
public class MinOperations {

    public static void main(String[] args) {
        MinOperations test = new MinOperations();

        // 2
//        int[] target = {5, 1, 3};
//        int[] arr = {9, 4, 2, 3, 4};

        // 3
//        int[] target = {6, 4, 8, 1, 3, 2};
//        int[] arr = {4, 7, 6, 2, 3, 8, 6, 1};

        // 7
        int[] target = {995168292, 13690313, 293160801, 642482000, 810529261, 98173438, 456394738, 882168981, 961299834, 794671198};
        int[] arr = {13690313, 794671198, 957156640, 882168981, 882168981, 293160801, 794671198, 111281680, 293160801, 642482000};

        int i = test.minOperations(target, arr);
        System.out.println(i);
    }

    public int minOperations(int[] target, int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        int length = target.length;
        for (int i = 0; i < length; i++) {
            map.put(target[i], i);
        }
        int size = 0;
        for (int i : arr) {
            if (map.containsKey(i)) {
                size++;
            }
        }
        if (size == 0) {
            return target.length;
        }
        int[] values = new int[size];
        int index = 0;
        for (int i : arr) {
            Integer v = map.get(i);
            if (v != null) {
                values[index++] = v;
            }
        }
        index = 0;
        for (int i = 1; i < size; i++) {
            int v = values[i];
            int last = values[index];
            if (v > last) {
                values[++index] = v;
            } else if (v < last) {
                int t = find(values, v, index);
                if (t > 0 && (values[t - 1] == v)) {
                    continue;
                }
                values[t] = v;
            }
        }
        return length - index - 1;
    }

    private int find(int[] values, int t, int end) {
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (values[m] > t) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

}
